package org.example.lds240306.didi.test1;

import java.util.Arrays;

public class OverlapCounter {
    public static void main(String[] args) {
        int[] left = new int[]{1, 2, 2}; // 左边界数组
        int[] right = new int[]{2, 3, 4}; // 右边界数组

        // 计算每个点的重叠次数
        int[] overlapCount = calculateOverlapCount(left, right);

        // 打印每个点的重叠次数
        System.out.println(Arrays.toString(overlapCount));
    }

    private static int[] calculateOverlapCount(int[] left, int[] right) {
        // 确定数组的大小
        int max = Arrays.stream(right).max().getAsInt();

        // 创建差分数组
        int[] diff = new int[max + 2]; // 加2是因为需要考虑到边界情况

        for (int i = 0; i < left.length; i++) {
            diff[left[i]] += 1; // 左边界，区间开始
            diff[right[i] + 1] -= 1; // 右边界的下一个位置，区间结束
        }

        // 根据差分数组计算重叠次数
        int[] overlapCount = new int[max + 1]; // 存储每个点的重叠次数
        overlapCount[0] = diff[0]; // 初始化第一个元素
        for (int i = 1; i <= max; i++) {
            overlapCount[i] = overlapCount[i - 1] + diff[i];
        }

        return overlapCount;
    }
}
